切割问题——算法系列教程(c++版)

梦想不会自己发光，真正闪耀的是那个为梦狂奔的你。献给知行的孩子们！（Eric.He著）

一、分割回文串（LeetCode 131）

问题描述：

• 给你一个字符串 s，请你将 s 分割成一些 子串，使每个子串都是 回文串 。返回 s 所有可能的分割方案。
  • 回文串是向前和向后读都相同的字符串。如“level”、“noon”等
• 提示：
  • 1 <= s.length <= 16
  • s 仅由小写英文字母组成
• 示例 1：
  • 输入：s = "aab"
  • 输出：[["a","a","b"],["aa","b"]]
• 示例 2：
  • 输入：s = "a"
  • 输出：[["a"]]

算法解析：

1. 分割逻辑：用 start 指针标记当前分割的起始位置，从 start 开始遍历字符串，尝试将 s[start..i] 作为一个子串；
2. 回文校验：若 s[start..i] 是回文串，则将其加入当前分割路径，递归处理下一段（起始位置变为 i+1）；
3. 终止条件：当 start 遍历到字符串末尾时，说明当前分割方案所有子串都是回文，将路径加入结果集；
4. 回溯还原：递归返回后，撤销当前选择（从路径中移除最后一个子串），继续尝试下一个分割点。

#include <iostream>
#include <vector>
using namespace std;

vector<vector<string>> res_palindrome;
vector<string> path_palindrome;

// 校验s[start..end]是否为回文串（逐字符对比）
bool isPalindrome(const string& s, int start, int end) {
    while (start < end) {
        if (s[start++] != s[end--]) return false;
    }
    return true;
}

// 回溯函数：分割回文串
void palindrome(const string& s, int start) {
    if (start == s.size()) {
        res_palindrome.push_back(path_palindrome);
        return;
    }
    for (int i = start; i < s.size(); ++i) {
        if (!isPalindrome(s, start, i)) continue;
        path_palindrome.push_back(s.substr(start, i - start + 1));
        palindrome(s, i + 1);
        path_palindrome.pop_back();
    }
}

int main() {
    string s="aab";
    palindrome(s,0);
    for(vector<string> item : res_palindrome)
    {
        cout << "[";
        for(string node : item )
        {
            cout << " "<< node << " ";
        }
        cout << "]" << endl;
    }

    return 0;
} 
        

输出结果

[ a  a  b ]
[ aa  b ]
        

二、复原 IP 地址（LeetCode 93）

问题描述：

• 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
  • 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
  • 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
• 提示：
  • 1 <= s.length <= 20
  • s 仅由数字组成
• 示例 1：
  • 输入：s = "25525511135"
  • 输出：["255.255.11.135","255.255.111.35"]
• 示例 2：
  • 输入：s = "0000"
  • 输出：["0.0.0.0"]
• 示例 3：
  • 输入：s = "101023"
  • 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]

算法解析：

IP 地址的约束非常明确，回溯的核心是「分割字符串为 4 个合法段」，具体思路：

1. 分割逻辑：用 start 标记当前分割的起始位置，用 count 记录已分割的段数（目标是分割为 4 段）；
2. 合法段校验：从 start 开始截取 1~3 个字符作为当前段（IP 段长度最大为 3），需满足 3 个条件：
   • 长度合法：1~3 个字符；
   • 数值合法：0 ≤ 数值 ≤ 255；
   • 格式合法：段长度 > 1 时，不能以 '0' 开头（如 "01" 是非法段）；
3. 终止条件：
   • 成功：count == 4 且 start 遍历到字符串末尾 → 生成有效 IP，加入结果集；
   • 失败：count > 4 或 start 超出字符串长度 → 剪枝返回；
4. 回溯还原：递归返回后，撤销当前选择（移除拼接的段和 '.'），继续尝试下一个分割长度。

#include <iostream>
#include <vector>
#include <string>

using namespace std;

vector<string> res_ip;  // 存储所有有效IP地址

// 回溯函数：
// s: 原始字符串
// start: 当前分割的起始索引
// path: 当前拼接的IP路径（如 "192.168"）
// count: 已分割的段数（目标是4段）
void ipAddresses(const string& s, int start, string path, int count) {
    // 剪枝：段数超过4，直接返回
    if (count > 4) return;
    // 终止条件：段数=4且遍历完字符串，找到有效IP
    if (count == 4 && start == s.size()) {
        res_ip.push_back(path);
        return;
    }

    // 遍历当前段的可能长度：1~3个字符（IP段最大长度为3）
    for (int len = 1; len <= 3; ++len) {
        // 剪枝：截取长度超出字符串范围，直接break
        if (start + len > s.size()) break;
        // 截取当前段
        string seg = s.substr(start, len);
        // 校验当前段是否合法：
        // 1. 长度>1时，不能以'0'开头（如"01"非法）
        // 2. 数值必须≤255
        if ((len > 1 && seg[0] == '0') || (len == 3 && stoi(seg) > 255)) {
            continue;
        }

        // 拼接路径：非最后一段需加'.'，最后一段不加
        string newPath = path + seg + (count == 3 ? "" : ".");
        // 递归：处理下一段，段数+1，起始索引+当前段长度
        ipAddresses(s, start + len, newPath, count + 1);
        // 回溯：无需显式还原（path是值传递，递归返回后自动恢复）
    }
}

int main() {
    string s="25525511135";
    // 剪枝：IP地址总长度范围是4~12（4段×1位 ~ 4段×3位）
    if (s.size() < 4 || s.size() > 12) return;

    // 从起始索引0、空路径、0段开始回溯
    ipAddresses(s, 0, "", 0);

    for(string item : res_ip)
    {
        cout << " [";
        cout << " " << item << " ";
        cout << "] " << endl;
    }

    return 0;
}
        

输出结果

[ 255.255.11.135 ]
[ 255.255.111.35 ]
            

三、单词拆分 II（LeetCode 140）

问题描述：

• 给定一个字符串 s 和一个字符串字典 wordDict ，在字符串 s 中增加空格来构建一个句子，使得句子中所有的单词都在词典中。以任意顺序 返回所有这些可能的句子。
• 提示：
  • 词典中的同一个单词可能在分段中被重复使用多次。
  • 1 <= s.length <= 20
  • 1 <= wordDict.length <= 1000
  • 1 <= wordDict[i].length <= 10
  • s 和 wordDict[i] 仅有小写英文字母组成
  • wordDict 中所有字符串都 不同
• 示例 1：
  • 输入:s = "catsanddog", wordDict = ["cat","cats","and","sand","dog"]
  • 输出:["cats and dog","cat sand dog"]
• 示例 2：
  • 输入:s = "pineapplepenapple", wordDict = ["apple","pen","applepen","pine","pineapple"]
  • 输出:["pine apple pen apple","pineapple pen apple","pine applepen apple"]
  • 解释: 注意你可以重复使用字典中的单词。
• 示例 3：
  • 输入:s = "catsandog", wordDict = ["cats","dog","sand","and","cat"]
  • 输出:[]

算法解析：

直接回溯会因重复子问题导致超时（比如多次处理 s[5..n] 的拆分），因此需要记忆化搜索（Memoization） 优化，核心思路：

1. 拆分逻辑：从字符串的 start 位置开始，尝试截取 s[start..i] 作为候选单词；
2. 字典校验：若候选单词在字典中，则递归处理剩余子串 s[i+1..n-1]；
3. 记忆化优化：用 memo[start] 存储 s[start..n-1] 的所有合法拆分结果，避免重复计算；
4. 终止条件：当 start == s.size() 时，返回包含空字符串的列表（表示找到一个合法拆分的末尾）；
5. 结果拼接：将当前合法单词与剩余子串的拆分结果拼接，形成完整的拆分方案。

关键优化点：

1. 哈希集合存储字典：将 wordDict 转为 unordered_set，实现 O(1) 时间校验单词是否存在；
2. 记忆化数组：memo[start] 记录 s[start..] 的拆分结果，后续遇到相同 start 直接返回结果，无需重复递归；
3. 提前剪枝：只截取长度不超过字典中最长单词的子串（避免无效截取）。

#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>

using namespace std;

unordered_set<string> wordSet;  // 字典的哈希集合，快速校验单词
unordered_map<int, vector<string>> memoVal;  // 记忆化：memo[start]存储s[start..]的拆分结果
int maxWordLen;  // 字典中最长单词的长度，用于剪枝

// 递归函数：返回s[start..n-1]的所有合法拆分方案
vector<string> wordBreak(const string& s, int start) {
    // 记忆化：已计算过s[start..]的结果，直接返回
    if (memoVal.count(start)) return memoVal[start];
    // 终止条件：start到达末尾，返回包含空字符串的列表（用于拼接）
    if (start == s.size()) return {""};

    vector<string> res;  // 存储s[start..]的所有拆分结果
    // 遍历截取的结束位置，剪枝：最多截取到start + maxWordLen
    for (int i = start; i < s.size() && i < start + maxWordLen; ++i) {
        string word = s.substr(start, i - start + 1);
        // 候选单词不在字典中，跳过
        if (!wordSet.count(word)) continue;

        // 递归处理剩余子串s[i+1..]
        vector<string> subRes = wordBreak(s, i + 1);
        // 拼接当前单词和剩余子串的拆分结果
        for (string& sub : subRes) {
            if (sub.empty()) {
                // 剩余子串为空，直接添加当前单词
                res.push_back(word);
            } else {
                // 拼接：当前单词 + 空格 + 剩余子串的拆分结果
                res.push_back(word + " " + sub);
            }
        }
    }
    // 记忆化存储：记录s[start..]的拆分结果
    memoVal[start] = res;
    return res;
}

int main() {
    vector<string> res;
    string s="catsanddog";
    vector<string> wordDict={"cat","cats","and","sand","dog"};

    // 1. 初始化字典集合
    for (string& word : wordDict) {
        wordSet.insert(word);
        // 2. 计算字典中最长单词的长度，用于剪枝
        maxWordLen = max(maxWordLen, (int)word.size());
    }
    // 3. 从start=0开始递归拆分
    res = wordBreak(s, 0);
    for(string item : res)
    {
        cout << " [";
        cout << " " << item << " ";
        cout << "] " << endl;
    }

    return 0;
}
        

输出结果

[ cat sand dog ]
[ cats and dog ]